// #include <stdio.h>      // 提供 printf 等函数（若需要调试可用）
// #include <stdlib.h>     // 提供 malloc、free 等动态内存函数
// #include "uthash.h"     // 提供哈希表功能，如 HASH_ADD_INT、HASH_FIND_INT、HASH_ITER、HASH_DEL

// step 1# 定义宏函数，取两个数的较大值
#define MAX(a, b) ((b) > (a) ? (b) : (a))

// step 2# 定义哈希表节点结构体
typedef struct {
    int key;              // 哈希集合中存储的整数值
    UT_hash_handle hh;    // uthash 管理哈希表所需的句柄
} HashEntry;

// step 3# 主函数，查找最长连续序列长度
int longestConsecutive(int* nums, int numsSize) {
    HashEntry* hashSet = NULL; // 初始化哈希集合为空
    HashEntry* e;

    // step 4# 构建哈希集合，去重保存所有数字
    for (int i = 0; i < numsSize; i++) {
        HASH_FIND_INT(hashSet, &nums[i], e); // 查找 nums[i] 是否已在哈希集合中
        if (e == NULL) {
            e = malloc(sizeof(HashEntry));   // 若不存在则分配内存
            e->key = nums[i];                // 记录键值
            HASH_ADD_INT(hashSet, key, e);   // 插入到哈希集合中
        }
    }

    // step 5# 遍历集合，查找以每个数为起点的最长连续序列
    int ans = 0; // 记录最长连续序列的长度
    HashEntry* tmp;

    HASH_ITER(hh, hashSet, e, tmp) {           // 遍历每个哈希节点
        int x = e->key;
        int y = x - 1;
        HASH_FIND_INT(hashSet, &y, e);         // 判断 x-1 是否存在
        if (e) {
            continue; // 若存在，则不是连续序列的起点，跳过
        }

        // step 5.1# 从 x 开始扩展连续序列
        y = x;
        do {
            y++;
            HASH_FIND_INT(hashSet, &y, e);     // 查找 y 是否存在于集合中
        } while (e);

        // step 5.2# y-1 是连续序列的最后一个数
        ans = MAX(ans, y - x); // 更新最长长度
    }

    // step 6# 清理哈希集合，防止内存泄漏
    HASH_ITER(hh, hashSet, e, tmp) {
        HASH_DEL(hashSet, e);  // 从哈希集合中移除该元素
        free(e);               // 释放内存
    }

    // step 7# 返回最终结果
    return ans;
}
